package com.ywk.base.dataStructure.linkedlist;

public class DoubleLinkedListDemo {

	public static void main(String[] args) {
		Node n1=new Node(1, "al");
		Node n2=new Node(2, "df");
		Node n3=new Node(3, "fr");
		Node n4=new Node(4, "we");
		Node n5=new Node(5, "gf");
		
		Node n6=new Node(6, "yt");
		Node n7=new Node(7, "ac");
		Node n8=new Node(8, "we");
		Node n9=new Node(9, "ht");
		DoubleLinkedList dl=new DoubleLinkedList();
		dl.addNode(n5);
		dl.addNode(n8);
		dl.addNode(n3);
		dl.addNode(n6);
		System.out.println("原双链表：");
		dl.showDoubleLinkedList();
		
		System.out.println("采用递归遍历的双链表：");
		dl.recursionErgodic();
		dl.recursionSearch(6);
		
		dl.deleteNode(n6);
		dl.deleteNode(n9);
		System.out.println("删除后的双链表：");
		dl.showDoubleLinkedList();
		
		CircleDoubleLinkedList cdl=new CircleDoubleLinkedList();
		cdl.addNode(n7);
		cdl.addNode(n9);
		cdl.addNode(n2);
		cdl.addNode(n4);
		System.out.println("原循环双链表：");
		cdl.showCircleDoubleLinkedList();
		
	}
	
}

class DoubleLinkedList{
	private Node head=new Node(0, "");
	
	public void addNode(Node n) {
		Node p=head.next;
		if(p==null) {
			head.next=n;
			n.pre=head;
			n.next=null;
			return;
		}
		while(true) {
			if(n.getNo()<p.getNo()) {
				n.next=p;
				p.pre.next=n;
				n.pre=p.pre;
				p.pre=n;//此句必须写在最后面（关键），上面的三句顺序可以变
				break;
			}else if(p.next==null) {
				p.next=n;
				n.pre=p;
				n.next=null;
				break;
			}
			p=p.next;
		}
	}
	
	public void showDoubleLinkedList() {
		Node p=head.next;
		while(true) {
			System.out.println(p);
			if(p.next==null) {
				break;
			}
			p=p.next;
		}
	}
	
	//双链表采用递归遍历(不用借助辅助指针)
	public void recursionErgodic() {
		if(head.next!=null) {
			head.next.ergodic();
		}
	}
	
	//双链表采用递归查询
	public void recursionSearch(int no) {
		Node result;
		if(head.next!=null) {
			result=head.next.search(no);
			if(result!=null) {
				System.out.println("找到了"+result);
			}else {
				System.out.println("不存在");
			}
		}
	}
	
	public void deleteNode(Node n) {
		Node p=head.next;
		while(true) {
			if(p.getNo()==n.getNo()) {
				if(p.next==null) {//删除的是最后的结点
					p.pre.next=null;
					p.pre=null;
					break;
				}
				p.pre.next=p.next;
				p.next.pre=p.pre;
				break;
			}else if(p.next==null){
				System.out.println("不存在该结点");
				break;
			}
			p=p.next;
		}
	}
}
	
class CircleDoubleLinkedList{
	private Node head;

	public CircleDoubleLinkedList() {
		super();
		head=new Node();
		//等号左边是指针，右边是实例对象，所以不能写成head.next=head.pre;
		head.next=head;
		head.pre=head;
	}
	
	public void addNode(Node n) {
		Node p=head.next;
		if(p==head) {
			head.next=n;
			n.pre=head;
			head.pre=n;
			n.next=head;
			return;
		}
		while(true) {
			if(n.getNo()<p.getNo() || p.next==head) {
				n.next=p;
				n.pre=p.pre;
				p.pre.next=n;
				p.pre=n;
				break;
			}
			p=p.next;
			if(p==head) {
				break;
			}
		}
	}
	
	public void showCircleDoubleLinkedList() {
		Node p=head.next;
		if(p==head) {
			System.out.println("空双链表");
			return;
		}
		while(true) {
			System.out.println(p);
			if(p.next==head) {
				break;
			}
			p=p.next;
		}
	}
	
	
	
	//计算链表长度
	public int size() {
		int count=0;
		Node p=head.next;
		if(p==head) {
			return count;
		}
		while(true) {
			count++;
			if(p.next==head) {
				break;
			}
			p=p.next;
		}
		return count;
	}
}	
	
	
	
	
class Node{
	private int no;
	private String name;
	public Node pre;
	public Node next;
	
	
	
	public Node() {
		super();
	}

	public Node(int no, String name) {
		super();
		this.no = no;
		this.name = name;
	}
	
	public int getNo() {
		return no;
	}

	public void setNo(int no) {
		this.no = no;
	}

	public String getName() {
		return name;
	}

	public void setName(String name) {
		this.name = name;
	}

	public Node getPre() {
		return pre;
	}

	public Node getNext() {
		return next;
	}

	@Override
	public String toString() {
		return "Node [no=" + no + ", name=" + name + "]";
	}
	
	//双链表采用递归遍历
	public void ergodic() {
		System.out.println(this);
		if(this.next!=null) {
			this.next.ergodic();
		}
	}

	//双链表采用递归查询
	public Node search(int no) {
		if(this.getNo()==no) {
			return this;
		}
		if(this.next!=null) {
			return this.next.search(no);//当递归中需要返回值时，递归方法前面一定要加return
		}
		return null;
	}
}

